This invention relates to frequency hopping (FH) radio systems. In particular, it relates to multiple, uncoordinated FH radios that try to form a wireless network. The invention describes how links between several FH radios can be established and maintained.
Radio Local Area Networks (radio LANs or RLANs) typically cover an area of technology where the computer industry and the wireless communications industry merge. Conventional computer networking has relied on wired LANs, typically packet-switched and designed for data transfer. By contrast, wireless networking (particularly cellular networking) has relied on wide area networks, typically circuit-switched and designed for voice transfer. Most efforts in the design of radio LANs have followed the design principles that are used in wired LANs. However, the best wireless network design may not be obtained using the wired LAN design principles because the environments are different in the wired medium and the wireless medium. Moreover, multimedia communications require additional features due to the special data traffic requirements of data, voice and video. Also, the residential environment has unique requirements that can impact the design of the system.
Almost all of the computer networks today use a wired infrastructure. The wired medium can range from a simple twisted pair to an optical fiber. Due to its shielded and controllable environment, the wired medium has low interference levels and stable propagation conditions. Consequently, the wired medium has potential for high to very high data transmission rates. Within the wired infrastructure, all participants in wired LANs typically share this single medium. The medium constitutes a single channel which is used by only a single one of a number of different users at any given time. To expand user access, time-division multiplexing (TDM) is used to allow different users to access the same channel at different times. The protocols for accessing wired media have been standardized by the IEEE in its 802 series of standards. Typically, multiple access reservation techniques like carrier sensing (e.g., Ethernet, 802.3 Carrier-Sense Multiple Access/Collision Detect (CSMA/CD)) or tokens (e.g., 802.4 token buses, or 802.5 token rings) are used to gain access to the medium. These protocols are used in a distributed sense such that the user occupying the channel reserves the medium by its present transmission or by its token. Using these protocols, every user can hear all data traffic that is transferred on the LAN. In a single LAN, all of the users share not only the channel, but also can access all of the information carried on that channel as well. As the number of users grows, the LAN can be divided into smaller LANs or segments that have independently operating channels. The individual LANs can be interconnected via bridges or routers that form interfaces between the different local networks. These configurations result in more complex networks (see, for example, D. Bertsekas and R. Callager, xe2x80x9cData Networksxe2x80x9d, 2nd Edition, Prentice-Hall, London, 1992). In discussing residential LANs it is sufficient here to consider a single LAN.
Each LAN typically provides a connectionless packet-switched service. Each packet has a destination address (and usually a source address as well) so that each user can determine whether or not each packet transferred on the LAN is intended for him. The net throughput per user in a single LAN is determined by the peak data rate on the channel and by the number of users that share this channel. Even if the peak data rate is very high (as is expected in the wired medium), the effective user throughput can be low if the channel has to be shared among many users.
Since the type of communication that takes place over wired LANs is typically asynchronous and connectionless, it is ill suited to support delay critical services like voice. Voice services demand synchronous or isochronous connections, which require priority techniques in the Medium Access Control (MAC) protocols. The priority techniques give voice users priority over non-voice users. Different studies evaluating existing data networks have shown that providing voice and other time sensitive data over existing data networks is a difficult task.
During the last several years, standards bodies in the United States and in Europe have worked on wireless LANs (WLANs). However, the United States and Europe have adopted different standards. In the United States, the WLAN standard is the IEEE 802.11 standard (see, Draft Standard IEEE 802.11, P802. 11/D1, Dec. 1994), whereas in Europe, the ETSI HIPERLAN standard has been developed for WLANs (see, ETSI, RES10/96/etr, xe2x80x9cRadio Equipment and Systems (RES); High Performance Radio Local Area Networks (HIPERLANs)xe2x80x9d, July 1996).
The IEEE 802.11 standard, as the name indicates, is an extension of the 802 LAN standard. The wireless connection is either a radio link or an infrared link. The radio link can be established using the Industrial, Scientific, Medical (ISM) band at 2.4 GHz. The standard provides for only a 1-2 Mb/s channel for each single WLAN at any given time. This relatively narrow bandwidth channel has to be shared among all users of the radio network. The standard defines both a configuration based on a wired infrastructure and a configuration based on an ad-hoc structure. With a wired infrastructure, the radio system merely provides a wireless extension between the wired LAN and the user terminal. Fixed access points interface between the wireline domain and wireless domain. In an ad-hoc network, wireless units create their own wireless network. No wired backbone is involved at all. It is the ad-hoc nature provided with wireless communications that gives the WLANs an important advantage over wired LANs in certain applications.
To avoid interference with other networks or other applications in the 2.4 GHz ISM band, either direct-sequence spreading or slow frequency hopping is used. Access to the channel is accomplished by a special form of Carrier-Sense Multiple Access/Collision Avoidance (CSMA/CA) that provides a connectionless service. In an architecture based on a wired infrastructure, the fixed part takes the role of a central controller which schedules all traffic. In an ad-hoc architecture, the distributed CSMA/CA protocol provides the multiple access to the channel. In general, the IEEE 802.11 standard is very similar to that of the wired Ethernet, except the wire has been replaced by a 1 Mb/s radio channel.
The effective user throughput decreases quickly as the number of participants increases. In addition, little immunity is provided against interference in the ISM band because the spreading factor for Direct Sequence Spread Spectrum (DSSS) is only 11 and the spreading factor for Frequency Hopping Spread Spectrum (FHSS) is only on the order of 79 channels. Different networks can theoretically coexist in the same area thereby increasing the aggregate throughput. The different networks either use different DSSS carrier frequencies of which seven are defined, or use different FHSS hop sequences. However, the aggregate throughput, defined as the average throughput per user times the number of collocated users (not necessarily participating in the same network), can never exceed 4-6 Mb/s with either technology (see, A. Kamerman, xe2x80x9cSpread-Spectrum Techniques Drive WLAN Performance,xe2x80x9d Microwaves and RF, Sept. 1996, pp. 109-114).
For collocating different networks under the IEEE 802.11 standard, it is preferred that the networks be based on a wired infrastructure. If a limited number of collocated fixed access points can create their own network, then a certain amount of coordination via the wired network is then possible. However, it is much more difficult to create ad-hoc networks under IEEE 802.11, because the MAC protocol does not lend itself to an ad-hoc structure. Instead of forming ad-hoc networks, units that come in range of an existing network will join the existing network and not create their own network.
HIPERLAN has followed a similar path as IEEE 802.11. The system operates in the 5.2 GHz band (not available in the United States). The standard is still under development and consists of a family of sub-standards, HIPERLAN 1 to 4. The most basic part, HIPERLAN I (ETSI, ETS300652, xe2x80x9cRadio Equipment and Systems (RES); High Performance Radio Local Area Networks (HIPERLAN) Type 1; Functional Specificationxe2x80x9d, June 1996), is similar to the IEEE 802.11. Again, a single channel is used, but with a higher peak data of 23.5 Mb/s. A dedicated CSMA/CA scheme is used, called Elimination-Yield Non-Preemptive Priority Multiple Access (EYNPMA) which provides for a number of contention-based phases before the channel is reserved. Although the 5.2 GHz band is unlicensed in Europe, only HIPERLAN-type applications are allowed. Therefore, no special measures are implemented against unknown jammers. Different networks can coexist in the same area provided different 23 MHz wide channels are used. Five such channels have been defined in the 5.2 GHz band. The HIPERLAN 2 standardization which concentrates on wireless Asynchronous Transfer Mode (ATM) is also relevant. Presumably, this wireless network will also use the 5.2 GHz band, will support peak data rates exceeding 40 Mb/s, and will use a centralized access scheme with some kind of demand assignment MAC scheme.
Both the existing WLAN and wired LAN systems have a single channel shared among all the participants of the local network. All users share both the medium itself and all information carried over this medium. In the wired LAN, this channel can encompass the entire medium. However, a single channel does not encompass the entire medium in WLANs in general and in particular in RLANs. In RLANs, the radio medium typically has a bandwidth of 80 to 100 MHz. Due to implementation limitations and cost of the radio transceivers and due to restrictions placed by regulatory bodies like the FCC and ETSI, it is virtually impossible to define a radio channel in the RLAN with the same bandwidth as the radio medium. Therefore, only part of the radio medium is used in a single RLAN. As a result, the peak data rate over the channel decreases. Also, the effective user throughput decreases because all participants share this channel, which is now much smaller than the medium. Although the medium is divided into different channels, each of which can be used to set up a different RLAN, in practice, only a single network covers a certain area, especially in ad-hoc networks. In RLANs based on a wired infrastructure, the different channels can be used to create cells, each cell is its own network that is not disturbed by neighboring cells. This result is achieved at the expense of predefining the allocation of channels. Thus, a cellular structure is created that prohibits the use of different ad-hoc radio networks in the same cell, thereby limiting the attainable aggregate throughput per unit area.
Ad-hoc networks by definition do not rely on the support of a wired infrastructure as is commonly used in cellular, cordless and WLAN systems. In cellular systems, access to the wired backbone is accomplished by access points or base stations. These base stations broadcast known control signals that the portable terminals can lock onto. Using the control signals, incoming and outgoing calls can be established and terminals can be directed to dedicated traffic channels. In conventional wireless systems, the activities of the base stations are highly coordinated.
In ad-hoc systems, the situation is completely different. Since ad-hoc systems are based on peer-to-peer connectivity, there is no difference between base stations and terminals (units). Any unit can operate as a base station to establish connections to other units. However, in a peer environment, it is unclear which unit should be the base station. It is also unclear how long a unit should be the base station after becoming one. It is undesirable to have each radio unit broadcast control information because it is not at all certain other units are around to receive this information. In addition, it consumes valuable (battery) power and creates unnecessary interference.
A system, known to the public as a BLUETOOTH(trademark) system, was recently introduced to provide ad-hoc connectivity between portable devices like mobile phones, laptops, Personal Digital Assistants (PDAs), and other mobile devices. This system uses frequency hopping and radios that are low-power, low-cost and have a small footprint. The BLUETOOTH(trademark) system supports both data and voice transmission. The latter are optimized by applying fast frequency hopping with a nominal rate of 800 hops/s through the entire 2.4 GHz ISM band in combination with a robust voice coding. Automatic retransmission is applied on data packets to combat packet failures due to collisions of different piconets (ad-hoc networks) TM visiting the same hop channel. An introduction to the BLUETOOTH(trademark) System can be found in xe2x80x9cBLUETOOTHxe2x80x94The universal radio interface for ad-hoc, wireless connectivity,xe2x80x9d by J. C. Haartsen, Ericsson Review No. 3, 1998.
A BLUETOOTH(trademark) system is a communication system that utilizes frequency hopping wireless technology. This system applies frequency hopping to enable the construction of low-power, low-cost radios with a small footprint. The system supports both data and voice. The latter are optimized by applying fast frequency hopping in combination with a robust voice coding. The frequency hopping has a nominal rate of 1600 hops per second (hops/s) through the entire 2.4 GHz ISM band, which is 80 MHz wide. Devices based on BLUETOOTH(trademark) wireless technology can create piconets, which comprise a master device and one or more slave devices connected via the FH piconet channel. The FH sequence used for the piconet channel is completely determined by the address or identity of the device acting as the master. The system clock of the master device determines the phase in the hopping sequence (i.e., the designation of which one of the possible hops in the sequence is the xe2x80x9ccurrentxe2x80x9d hop). In BLUETOOTH(trademark) wireless technology, each device has a free-running system clock. Each of the slave devices adds a corresponding time offset to its clock that enables it to become aligned with the clock of the master device. By using the master address to select the proper hopping sequence and by using the time offset to align to the master clock, each slave device keeps in hop synchrony to the master device; that is, master and slave devices remain in contact by hopping synchronously to the same hop frequency or hop carrier. A scatternet is a group of piconets. The aggregate and individual throughput of users in a scatternet is much greater than when each user participates on the same piconet with a 1 Mbit/s channel. For more details, reference is made to U.S. patent application Ser. No. 08/932,911, filed on Sep. 18, 1997 in the name of J. C. Haartsen and entitled xe2x80x9cFrequency Hopping Piconets in an Uncoordinated Wireless Multi-user System,xe2x80x9d which is hereby incorporated herein by reference in its entirety.
The BLUETOOTH(trademark) system also features low-power modes like HOLD and PARK where the slaves can be placed in a temporary suspend or low duty cycle tracking mode, respectively. The park mode is described in U.S. patent application Ser. No. 09/210,594 filed Dec. 15, 1998 entitled xe2x80x9cCentral Multiple Access Control for FH Radio Networks,xe2x80x9d by J. C. Haartsen and J. Elg, which is incorporated herein by reference in its entirety.
To find and connect different BLUETOOTH(trademark) units and form an ad-hoc network is not trivial. BLUETOOTH(trademark) units do not broadcast information when they are in standby. Instead, they periodically scan the spectrum for a very short duration. The low-duty cycle scan is important to keep power consumption to a minimum. By default, a BLUETOOTH(trademark) device scans one hop channel for about 11 ms every 1.28 seconds. Therefore, every 1.28 seconds a different hop channel is selected and scanned. The interval of 1.28 seconds can be increased up to 3.84 seconds in very low-power devices. This means that during 3.84 second intervals, the unit is in a sleep mode and cannot be reached by other BLUETOOTH(trademark) units. Since the BLUETOOTH(trademark) units do not routinely broadcast signals, another mechanism has been implemented to discover which units are in range. In this mechanism called inquiry, a request for information is broadcast by the inquirer. The request message can be sent at anytime, but is usually induced by a desire in the device (i.e., by an action of the user) to connect to other devices. On receipt of a request message, the receiving units return an information message including their identity and some more device-specific information. With this information, the inquirer can directly make contact to any of the units that replied using the access technique as described in U.S. Pat. No. 5,940,431 issued Aug. 17, 1999 entitled xe2x80x9cAccess technique of channel hopping communications systemxe2x80x9d by J. C. Haartsen and P. W. Dent, which is incorporated herein by reference in its entirety.
One issue concerning establishing connections among BLUETOOTH(trademark) wireless devices or similar FH wireless devices is the speed of the inquiry and page procedures. Since the BLUETOOTH(trademark) unit can sleep for 2.56 seconds between consecutive inquiry scans (i.e., when it scans for a dedicated inquiry message), it may take more than 10 seconds before all units in the surroundings have responded. For many applications, this is an undesirably large time span. Particularly in networking environments, the speed of establishing and releasing connections is preferably less than a second. Therefore, a system and method that accelerate the formation of a network of multiple FH units are needed.
It should be emphasized that the terms xe2x80x9ccomprisesxe2x80x9d and xe2x80x9ccomprisingxe2x80x9d, when used in this specification, are taken to specify the presence of stated features, integers, steps or components, but the use of these terms does not preclude the presence or addition of one or more other features, integers, steps, components or groups thereof.
The invention overcomes the prior art limitations by providing a method of establishing an anchor piconet comprising identifying a plurality of wireless units within range of one another. Then an anchor unit is selected from the plurality of wireless units. A beacon signal is generated from the anchor unit and the remaining wireless units are locked onto the beacon signal. An additional method of peer-to-peer ad-hoc networking comprises establishing at least one anchor piconet and establishing at least one traffic piconet between at least two wireless units in the anchor piconet using information relayed from the at least one anchor piconet to each wireless unit that participates in the traffic piconet.
The above features and advantages of the invention will be more apparent and additional features and advantages of the invention will be appreciated from the following detailed description of the invention made with reference to the drawings.